package com.dylan.历史.算法;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.ToString;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Auther: ankang
 * @Date: 2019/1/15 22:07
 * @Description:
 */
public class 构造哈夫曼树 {

    public static void main(String[] args) {
        List<Node> list = Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9).map(d -> Node.builder().data(d).build()).collect(Collectors.toList());
        createHuffman(list);
        System.out.println(list);
    }

    private static void createHuffman(List<Node> list) {
        if (list.size() <= 1) {
            return;
        }
        list.sort((n1, n2) -> n2.data - n1.data);
        Node n1 = list.remove(list.size()-1);
        Node n2 = list.remove(list.size()-1);
        Node n3 = Node.builder().data(n1.data + n2.data).left(n1).right(n2).build();
        list.add(n3);
        createHuffman(list);
    }

    @Builder
    @ToString
    static class Node {
        int data;
        Node left;
        Node right;
    }
}
